import java.util.HashSet;
import java.util.LinkedHashSet;

/**
 * @ClassName Offer52
 * @Description 剑指 Offer 52. 两个链表的第一个公共节点
 * @Author clockTown
 * @Date 2021/8/23 8:58
 * @Version 1.0
 */
class Offer52 {
}

/**
 * v0 哈希表
 */
class Offer52V0 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new LinkedHashSet<>();
        while (headA != null){
            set.add(headA);
            headA = headA.next;
        }
        while (headB != null){
            if (set.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}

/**
 * v1 双指针
 */
class Offer52V1 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null){
            return null;
        }

        ListNode pA = headA;
        ListNode pB = headB;

        while (pA != pB){
            pA = (pA == null) ? headB:pA.next;
            pB = (pB == null) ? headA:pB.next;
        }

        return pA;
    }
}